import java.util.*;

class Solution1212 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret1=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n-3;i++){
            while(i<n&&i>0&&nums[i]==nums[i-1]) i++;
            for(int j=i+1;j<n-2;j++){
                while(j<n-1&&j>i+1&&nums[j]==nums[j-1]) j++;
                int left=j+1,right=n-1;
                long target1=(long)target-nums[i]-nums[j];

                while(left<right){
                    if(target1==(long)nums[left]+nums[right]){
                        List<Integer> ret=new ArrayList<>();
                        ret.add(nums[i]);ret.add(nums[j]);ret.add(nums[left]);ret.add(nums[right]);
                        ret1.add(ret);
                        while(left<right&&nums[left]==nums[left+1]) left++;
                        left++;
                        while(right>left&&nums[right]==nums[right-1])   right--;
                        right--;
                    } else if(target1<nums[left]+nums[right]){
                        right--;

                    }
                    else {

                        left++;
                    }
                }
            }
        }
        return ret1;
    }
}
public class Test {
    public static String addBinary(String a, String b) {
        StringBuffer sb=new StringBuffer();
        int right=a.length()-1,right2=b.length()-1;
        int sum=0;
        while(right>=0||right2>=0||sum!=0){

            if(right>=0) {
                char hh=a.charAt(right--);

                sum += Integer.parseInt(String.valueOf(hh));
            }
            if(right2>=0) {
                char hh = b.charAt(right2--);
                sum += Integer.parseInt(String.valueOf(hh));
            }
            sb.append(sum%2);
            sum/=2;
        }
        return sb.reverse().toString();
    }
    public static int maxSubarraySumCircular(int[] nums) {
        if(nums.length==1) return nums[0];
        return  Math.max(maxSubarray(nums,0,nums.length),maxSubarray(nums,2,nums.length+1));
    }
    public static int maxSubarray(int[] nums,int left,int right){
        int[] dp=new int[right];
        dp[left]=nums[left];
        int index=left;
        for(int i=left+1;i<right;i++){
            left=i;
            if(left==nums.length) left=0;
            dp[i]=Math.max(nums[left],dp[i-1]+nums[left]);
        }
        int max=-0X3f3f3f3f;
        for(int i=index;i<right;i++){
            if(max<dp[i]) max=dp[i];
        }
        return max;
    }
    public static int maxSubarraySumCircular22(int[] nums) {
        int n=nums.length;
        int[] dp=new int[2*n];
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
        }
       int index=0;
        for(int i=n;i<2*n;i++){
            dp[i]=Math.max(dp[i-1]+nums[index],nums[index]);
            index++;
        }
        int max=-0x3f3f3f3f;
        for(int i=0;i<2*n;i++){
            if(dp[i]>max) max=dp[i];
        }
        return max;
    }

        public static int maxSubarraySumCircular33(int[] nums) {
            if(nums.length==1) return nums[0];
            int max=-0x3f3f3f3f;
            for(int i=0;i<nums.length;i++){
                int sum=maxSubarray1(nums,i,nums.length+i);
                max= Math.max(sum,max);
            }
            return  max;
        }
        public static int maxSubarray1(int[] nums,int left,int right){
            int[] dp=new int[right];
            dp[left]=nums[left];
            int index=left;
            int n=nums.length;
            for(int i=left+1;i<right;i++){
                left=i%n;
                dp[i]=Math.max(nums[left],dp[i-1]+nums[left]);
            }
            int max=-0X3f3f3f3f;
            for(int i=index;i<right;i++){
                if(max<dp[i]) max=dp[i];
            }
            return max;
        }
    public static boolean canJump(int[] nums) {
        int n=nums.length;
        boolean[] dp=new boolean[n];
        dp[0]=true;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(i<=nums[j]+j) dp[i]=dp[j];
            }

        }
        return dp[n-1];
    }
    public static void main(String[] args) {
       int[] nums={2,3,1,1,4};
        System.out.println(canJump(nums));
//       String a="1010";
//       String b="1011";
//     String ret=  addBinary(a,b);
//        System.out.println(ret);
//        Map<Integer,Set<Integer>> map=new HashMap<>();
//        map.put(1,new HashSet<>());
//        map.put(2,new HashSet<>());
//        map.get(1).add(3);
//        map.get(2).add(2);
//        map.get(2).add(1);
//  for(int x:map.get(2)){
//      System.out.println(x);
//  }

    }
}
